class Solution {
    public:
        int maxWidthRamp(vector<int>& nums) {
            stack<int> st;
            int ans = 0,n = nums.size();
            for(int i  = 0; i< n;i++){
                if(st.empty() || nums[st.top()] > nums[i]){
                    st.push(i);
                }
            }
    
    
            for(int i = n - 1;i >= 0;i--){
                while(!st.empty()&& nums[st.top()] <= nums[i]){
                    ans = max(ans, i - st.top());
                    // cout << i <<' '<<st.top() << endl;
                    st.pop();
                }
            }
            return ans;
        }
    };

1
class Solution {
    public:
        int longestWPI(vector<int>& hours) {
            int n =hours.size(),ans = 0,s[n + 1];
            stack<int> st;
            st.push(s[0] = 0);
            for(int i = 1;i <= n;i++){
                s[i] = s[i - 1] + (hours[i - 1] > 8 ? 1:-1);
                if(s[i] < s[st.top()]){
                    st.push(i);
                }
            }
            for(int i = n;i >= 0;i--){
                while(!st.empty() && s[i] > s[st.top()]){
                    ans = max(ans,i - st.top());
                    st.pop();
                }
            }
            return ans;
        }
    };

    class Solution {
        public:
            bool find132pattern(vector<int>& nums) {
                int n = nums.size();
                stack<int> st;
                // 插大的，降序
                int k = INT_MIN;
                for (int i = n - 1; i >= 0; i--) {
                    if (k > nums[i])
                        return true;
                    while (!st.empty() && nums[st.top()] < nums[i]) {
                        k = max(k, nums[st.top()]);
                        st.pop();
                    }
                    st.push(i);
                }
                return false;
            }
        };

        class Solution {
            public:
                long long numberOfSubarrays(vector<int>& nums) {
                    long long ans = 0;
                    int n = nums.size();
                    stack<pair<int,int>> st;
                    st.emplace(INT_MAX,0);
                    for(int i = 0;i < n;i++){
                        ans++;
                        while(st.top().first < nums[i]){
                            st.pop();
                        }
                        if(st.top().first == nums[i]){
                            ans += st.top().second++;
                        }else{
                            st.emplace(nums[i],1);
                        }
                    }
                    return ans;
                }
            };